package Queue;

import java.util.Stack;

/**
 *  题目 ：队列中可以看到的人数
 *  题目详述 ：
 *  有n个人排成一个队列，从左到右编号为0到n - 1。给你以一个整数数组heights，每个整数 互不相同，heights[i]表示第i个人的高度。
 * 一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人矮。
 * 更正式的，第i个人能看到第j个人的条件是i < j且min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1])。
 * 请你返回一个长度为 n的数组answer，其中answer[i]是第i个人在他右侧队列中能看到的人数。
 */
public class P1944 {
    /**
     * 核心思想 ：
     *  使用单调栈来实现；
     *  （1）由于左侧height[i]能够看见右侧递增的人，即左侧的人只能够看见右侧逐渐递增的人；
     *   (2) 通过将height数组中的元素逆序插入，形成单调递减栈
     *   （即，若是插入较大的元素时，需要将单调递减栈中小于其的元素进行弹栈，从而来满足单调递减栈）
     *   注意 ：
     *    满足的条件 ： （由于每个人的身高都不重复，即不会出现身高相等的情况）
     *    左边的第i个人能够看见右边的第j个人条件为  ===》 i 和 j之间的所有人身高小于 第i/j个人的身高
     * @param heights
     * @return
     */
    public int[] canSeePersonsCount(int[] heights) {
        int length = heights.length; // 获取目标数组大小
        Stack<Integer> stack = new Stack<>(); // 初始化单调递减栈
        int[] result = new int[length]; // 初始化结果数组
        /**
         *  逆序对于整个height进行遍历
         *  目的 ：
         *  （1）若是逆序进行遍历的话，由于结果数组result是从左向右统计人数；
         *  （2）即，逆序插入的话，能够在构建单调递减栈时，同时对于结果数组进行赋值
         */
        for(int i = length - 1 ; i >= 0 ; i--){
            while (!stack.isEmpty() && heights[i] > stack.peek()){
                // 即，满足栈不为空，同时所要逆序插入的元素 > 栈顶元素的值，
                // 为满足栈为单调递减栈，所以需要将栈中较小的元素弹栈；
                result[i]++;
                stack.pop();
            }
            // 由于上述循环并不会去将单调递减栈中的元素，累加到result数组上
            // 此种情况 ：等价于 （1）能够仰视看见所有矮于其（满足逐渐递增）的人，（2）同时能够看见第一个比其高的人
            result[i] += stack.isEmpty() ? 0 : 1;
            // 特殊情况 ：等价于 （1）能够仰视看见所有矮于其（满足逐渐递增）的人，（2）同时能够看见所有比其高的人（单调递减栈中元素）
            //result[i] += stack.size();
            stack.push(heights[i]);
        }
        return result;
    }
}
